package greedy;

import java.util.Arrays;

/**
 * @author : Rookie
 * @description : K次取反后最大化的数组和
 * @date : 2023/12/27
 */
public class LargestSumAfterKNegations {

    public static void main(String[] args) {
        int[] nums = new int[] {4,2,3};
        int k = 1;
        // 按绝对值从大到小排序
        sortByAbs(nums);
        // 将topk的 小于0的值翻转
        for (int i = 0; i < nums.length; i++) {
            if (k>0 && nums[i] <0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        // 用完最后的取反次数
        while (k>0) {
            int minIndex = getMinIndex(nums);
            nums[minIndex] = -nums[minIndex];
            k--;
        }
        Arrays.stream(nums)
                .reduce(Integer::sum)
                .ifPresent(System.out::println);
    }

    private static int getMinIndex(int[] nums) {
        int minIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }
        return minIndex;
    }

    private static void sortByAbs(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int maxValIndex = i;
            for (int j = i; j < nums.length; j++) {
                if (Math.abs(nums[maxValIndex]) < Math.abs(nums[j])) {
                    maxValIndex = j;
                }
            }
            swap(nums,maxValIndex,i);
        }
    }

    private static void swap(int[] nums,int i,int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
